DROPS

Document

DOI: 10.4230/LIPIcs.CSL.2024.11

Active Learning of Deterministic Transducers with Outputs in Arbitrary Monoids

Authors: Quentin Aristote

Published in: LIPIcs, Volume 288, 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024)

Abstract

We study monoidal transducers, transition systems arising as deterministic automata whose transitions also produce outputs in an arbitrary monoid, for instance allowing outputs to commute or to cancel out. We use the categorical framework for minimization and learning of Colcombet, Petrişan and Stabile to recover the notion of minimal transducer recognizing a language, and give necessary and sufficient conditions on the output monoid for this minimal transducer to exist and be unique (up to isomorphism). The categorical framework then provides an abstract algorithm for learning it using membership and equivalence queries, and we discuss practical aspects of this algorithm’s implementation.

Cite as

Quentin Aristote. Active Learning of Deterministic Transducers with Outputs in Arbitrary Monoids. In 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 288, pp. 11:1-11:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{aristote:LIPIcs.CSL.2024.11,
  author =	{Aristote, Quentin},
  title =	{{Active Learning of Deterministic Transducers with Outputs in Arbitrary Monoids}},
  booktitle =	{32nd EACSL Annual Conference on Computer Science Logic (CSL 2024)},
  pages =	{11:1--11:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-310-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{288},
  editor =	{Murano, Aniello and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2024.11},
  URN =		{urn:nbn:de:0030-drops-196545},
  doi =		{10.4230/LIPIcs.CSL.2024.11},
  annote =	{Keywords: transducers, monoids, active learning, category theory}
}

Search Results

Documents authored by Aristote, Quentin

Active Learning of Deterministic Transducers with Outputs in Arbitrary Monoids

Abstract

Cite as

Thanks for your feedback!

Could not send message